import sun.awt.geom.AreaOp;
import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * @User: vitobo
 * @Date: 2024-07-01
 * @Description: 实现二叉搜索树
 */

class SearchTree{
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root = null;

    /**
     *  查找一个val 是否在当前的搜索树中
     *  没有时返回null
     * @param val
     * @return
     */
    public TreeNode search(int val){
        TreeNode cur = root;
        while (cur != null){
            if(cur.val < val){
                cur = cur.right;
            }else if(cur.val > val){
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

    /**
     *  插入元素key
     * @param key
     * @return
     */
    public boolean insert(int key){
        if(root == null){
            root = new TreeNode(key);
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null){
            if(cur.val < key){
                parent = cur;
                cur = cur.right;
            } else if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            }else {
                return false; // 相同的key是不能进行插入的
            }
        }

        // 此时 cur=null
        TreeNode node = new TreeNode(key);
        if(key < parent.val){
            parent.left = node;
        }else {
            parent.right = node;
        }

        return true;
    }

    // 中序遍历二叉搜索树
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    /**
     * 删除一个节点
     * @param key
     */
    public void remove(int key){
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null){
            if(cur.val == key){
                removeNode(parent, cur);
            } else if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    private void removeNode(TreeNode parent, TreeNode cur){
        if(cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if(cur == parent.left){
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if(cur == root){
                root = cur.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while (target.left != null){
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left){
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }

    }
}


public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("abc", 2);
        map.put("abcd", 3);
        map.put("wto", 5);

        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        for(Map.Entry<String, Integer> entry : entrySet){
            System.out.println("key: " + entry.getKey() + " val: " + entry.getValue());
        }
    }

    public static void main2(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("hello", 2);
        map.put("wold", 4);

        Integer v = map.getOrDefault("hello1", 200);
        System.out.println(v);

        System.out.println("取出key值, 进行组织, 通过set");
        Set<String> set = map.keySet();
        System.out.println(set);

        Collection<Integer> collection = map.values();
        System.out.println(collection);
    }


    public static void main1(String[] args) {
        SearchTree searchTree = new SearchTree();
        int[] array = {5,2,3,4,1,7,8,2,6,0,9};
        for (int i = 0; i < array.length; i++) {
            searchTree.insert(array[i]);
        }
        searchTree.inorder(searchTree.root);
    }
}
